//二叉树中的最大路径和
class Solution {
public:
    int maxSum = INT_MIN;
    int maxGain(TreeNode* root)
    {
        if(!root){
            return 0;
        }
        int leftMax = maxGain(root->left);
        int rightMax = maxGain(root->right);
        maxSum = max(maxSum,root->val + leftMax + rightMax); //尝试更新最大路径
        return (root->val + max(leftMax,rightMax) < 0) ? 0 : (root->val + max(leftMax,rightMax));//返回的值必须>=0
    }
    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return maxSum;
    }
};